/**
 * 排序工具类
 * @author liu_jshan
 * @version 1.0 20240324
 */

import randomUtil from "./randomUtil";

/**
 * 默认比较方法
 * @param {*} a 元素1
 * @param {*} b 元素2
 * @returns 1 | 0 | -1
 */
function basicSortFunction(a, b) {
    if (a > b) return 1
    else if (a === b) return 0
    else return -1
}

/**
 * 元素交换
 * @param {*} array 数组
 * @param {*} i 索引i
 * @param {*} j 索引j
 */
function swap(array, i, j) {
    let temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

/**
 * 冒泡排序
 * @param {*} array 需要排序数组
 * @param {*} sortFun 比较方法 function(a, b) return >0 | 0 | <0
 */
function bubbleSort(array, sortFun) {
    if (!sortFun) sortFun = basicSortFunction
    let sortFinish = false
    while (!sortFinish) {
        sortFinish = true
        for (let i = 0; i < array.length - 1; i++) {
            if (sortFun(array[i], array[i + 1]) > 0) {
                swap(array, i, i + 1)
                sortFinish = false
            }
        }
    }
}

/**
 * 直接插入排序
 * @param {*} array 需要排序数组
 * @param {*} sortFun 比较方法 function(a, b) return >0 | 0 | <0
 */
function insertionSort(array, sortFun) {
    basicInsertionSort(array, 1, sortFun)
}

/**
 * 希尔排序
 * @param {*} array 需要排序数组
 * @param {*} sortFun 比较方法 function(a, b) return >0 | 0 | <0
 */
function shellSort(array, sortFun) {
    let increment = array.length
    while ((increment /= 2) >= 1) basicInsertionSort(array, increment, sortFun)
}

/**
 * 基本插入排序
 * @param {*} array 需要排序数组
 * @param {*} increment 增量
 * @param {*} sortFun 比较方法 function(a, b) return >0 | 0 | <0
 */
function basicInsertionSort(array, increment, sortFun) {
    if (!sortFun) sortFun = basicSortFunction
    //i为需要插入的元素, j为有序序列的末尾元素
    for (let i = increment; i < array.length; i++) {
        let needInsert = array[i];
        let j = i - increment;
        while (j >= 0 && sortFun(array[j], needInsert) > 0) {
            array[j + increment] = array[j];
            j -= increment;
        }
        array[j + increment] = needInsert;
    }
}

/**
 * 快速排序
 * @param {*} array 需要排序数组
 * @param {*} sortFun 比较方法 function(a, b) return >0 | 0 | <0
 */
function quickSort(array, sortFun) {
    if (!sortFun) sortFun = basicSortFunction
    quickSortBasic(array, 0, array.length - 1, sortFun)
}

/**
 * 快速排序
 * @param {*} array 需要排序数组
 * @param {*} left 排序开始索引
 * @param {*} right 排序开始结束
 * @param {*} sortFun 比较方法 function(a, b) return >0 | 0 | <0
 */
function quickSortBasic(array, left, right, sortFun) {
    let low = left
    let high = right
    let pivot = array[randomUtil.randomNumberRange(left, right + 1)] //基准
    while (low < high) {
        while (low < high && sortFun(array[high], pivot) > 0) high--
        while (low < high && sortFun(array[low], pivot) < 0) low++
        swap(array, low, high)
    }
    array[low] = pivot
    if (low > left) quickSortBasic(array, left, low - 1, sortFun)
    if (high < right) quickSortBasic(array, high + 1, right, sortFun)
}

const sortUtil = {
    bubbleSort,
    insertionSort,
    shellSort,
    quickSort
}
export default sortUtil